package com.lijing.QuickSort;

public class Quick {

    /**
     * 排序arr所有元素
     * @param arr 数组
     */
    public static void sort(Comparable[] arr){
        int lo = 0;
        int hi = arr.length-1;
        sort(arr,lo, hi);
    }

    /**
     * 排序lo-hi之间的元素
     * @param arr
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] arr, int lo, int hi){
        if (hi <= lo){
            return;
        }
        int index = partition(arr, lo, hi);
        sort(arr,lo,index-1);
        sort(arr,index+1,hi);
    }

    /**
     * 对数组arr中，从索引lo到hi之间的元素进行分组，并返回分组界限对应的索引
     * @param arr 数组
     * @param lo 开始索引
     * @param hi 结束索引
     * @return 返回分界处的索引
     */
    public static int partition(Comparable[] arr,int lo, int hi){
        Comparable temp = arr[lo];
        int left = lo;
        int right = hi+1;
        while (true){
            //先从右往左扫描
            while (less(temp,arr[--right])){
                if(right == lo){
                    break;
                }
            }
            //再从左往右扫描
            while(less(arr[++left],temp)){
                if(left == hi){
                    break;
                }
            }
            //当left>=right时结束
            if(right<=left){
                break;
            }else{
                exch(arr,left,right);
            }

        }
        exch(arr,lo,right);
        return right;
    }

    /**
     * 比较大小
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w)<0;
    }

    /**
     * 交换i,j索引处的值
     * @param arr
     * @param i
     * @param j
     */
    private static void exch(Comparable[] arr, int i, int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
